Unique binary search trees [Math]

Time: O(N); Space: O(1); medium

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example 1:

Input: n = 3

Output: 5

Explanation:

Given n = 3, there are a total of 5 unique BST’s:

1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

1. Recursion

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 1

        def combination(n, k):
            count = 1
            # C(n, k) = (n) / 1 * (n - 1) / 2 ... * (n - k + 1) / k
            for i in range(1, k + 1):
                count = count * (n - i + 1) / i
            return count

        return combination(2 * n, n) - combination(2 * n, n - 1)

2. Dynamic Programming

[3]:

class Solution2(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        counts = [1, 1]
        for i in range(2, n + 1):
            count = 0
            for j in range(i):
                count += counts[j] * counts[i - j - 1]
            counts.append(count)

        return counts[-1]

[4]:

s = Solution1()

n = 3
assert s.numTrees(n) == 5